1. Field of the Invention
The present invention relates to a method and a system for generating a test pattern used for fault detection or the like of a large scale integrated circuit (LSI) as well as a computer readable medium instructing the system to perform the method. More particularly, the invention relates to a method and a system suitable for the case where the entirety of an objective circuit for test pattern generation is divided into a plurality of subcircuits and a test pattern generating method and a system suited for generating test patterns for these subcircuits by means of distributed processing, as well as a computer readable medium instructing the system to perform the method.
2. Description of Related Art
Accompanying the increase in complexity and enlargement in scale of the integrated circuits such as LSIs, techniques are in fashion in which the entirety of an objective circuit for test pattern generation is divided into a plurality of subcircuits with a specified scale, and the test pattern generation for each subcircuit is processed distributedly by means of a plurality of computers. The inventor of the present invention and others disclosed such a method as Japanese Laid Open Patent Publication No. 11-211801 and No. 11-237450, which were laid open after the priority date of the present invention. Their invention has been filed in US patent application as Ser. No. 09/236,903. FIG. 11 shows a schematic configuration of such a test pattern generation system employing a circuit division distributed processing technique. As shown, in this test pattern generation system a plurality of engineering work stations (EWSs) are interconnected via a network NW such as a local area network (LAN). Note, however, that beside the mode shown in the figure, various kinds of other mode, such as one in which a plurality of central processing units (CPUs) are connected by busses to a single computer with multiprocessor configuration, are also conceivable.
In the figure, each of EWSs 1-1 to 1xe2x80x94n (n is a natural number) is a computer in charge of automatic generation processing of a test pattern, and performs at one point in time, test pattern generation for one subcircuit. In what follows, the CPU mounted on each EWS will be referred to as xe2x80x9cremote CPUxe2x80x9d. In general, the total number of subcircuits obtainable by circuit division is set to be a number far greater than the number n of the remote CPUs. On the other hand, EWS 1-0 is a computer which integrally controls the EWSs 1-1 to 1xe2x88x92n, and after division of the entirety of the object of test pattern generation into subcircuits, performs distributed processing of test pattern generation for the entire circuit by letting EWSs 1-1 to 1xe2x88x92n execute test pattern generation processing for respective subcircuits. In the following, the CPU mounted on the EWS 1-0 will be referred to as xe2x80x9clocal CPUxe2x80x9d.
The local CPU hands over information (xe2x80x9csubcircuit informationxe2x80x9d in the figure showing the constitution of the subcircuits and a collection of fault information (xe2x80x9cfault listxe2x80x9d in the figure) to be detected for respective subcircuits to each remote CPU, and requests them to generate test patterns for the subcircuits. The fault information includes fault position information for the entire circuit, identification information showing whether the fault is a xe2x80x9c1xe2x80x9d fault or a xe2x80x9c0xe2x80x9d fault, and the like. In the meantime, a remote CPU requested the processing by the local CPU generates a test pattern based on the received subcircuit information and fault list and sends the result back to the local CPU. In addition, it determines information on the faults which were undetectable by the generated test pattern and reports it back to the local CPU. Here, the local CPU is constantly watching the processing conditions to see whether respective remote CPUs are in the process of executing test pattern generation. Whenever the result of test pattern generation (pattern and undetected fault information) is reported back from some remote CPU, the local CPU retrieves remote CPUs in idle state which are not executing the test pattern generation processing, selects a subcircuit which has not yet completed the processing, and requests an idle remote CPU to generate a test pattern for that subcircuit.
Now, the size (here, the number of gates) of the subcircuit obtained by the circuit subdivision is calculated in advance to be a prescribed value based on the evaluation in consideration of obtaining the optimum processing efficiency of test pattern generation. Accordingly, the local CPU performs circuit subdivision so as to have the size of the subcircuit to be approximately equal to the prescribed value. In this case, a subcircuit is constructed by collecting a plurality of circuit blocks called xe2x80x9cconesxe2x80x9d which will be described later. In FIG. 12 which illustrates a circuit diagram for only a part extracted from the entire circuit which is the object of test pattern generation, symbols Ti1 to Ti7 are input terminals, symbols To1 and To2 are output terminals, and symbols 5-1 to 5-6 are logic gates. In addition, symbols 6-1 and 6-2 are circuit block composed of the input terminals, output terminal, and logic gates, which will be called cones in this invention, so named in association with the shapes of the cross section of cones along the axes. Moreover, since these input terminals and the output terminal act as the interfaces between the circuit as a whole and the outside, these are sometimes called external input terminals and an external output terminal.
The cones are in 1 to 1 correspondence with the output terminals, and a cone is defined as a set of all the logic gates passed through and all the input terminals arrived at, and the output terminal being the starting point, before one arrives at input terminals when one traces logic gates sequentially starting from an output terminal toward the input terminals. In other words, a cone is formed by the collection of all the logic gates and input terminals through which a logical value can be propagated to a certain output terminal, together with that output terminal. For example, when the paths within the circuit are traced with the output terminal To1 as a starting point, since the output terminal To1 is connected to the logic gate 5-1, the logic gate is included in the cone 6-1. Further, the logic gate 5-1 is connected to the input terminals Ti1 and Ti2 and the logic gate 5-2. Since, however, the logic gate 5-2 is not connected in the direction from the output terminal To1 to the input terminal, it is excluded and only the input terminals Ti1 and Ti2 are included in the cone 6-1. That is, the cone 6-1 is composed of the output terminal To1, the logic gate 5-1, and the input terminals Ti1 and Ti2. The cone 6-2 is formed by the same procedure, and it includes the output terminal To2, the logic gates 5-2 to 5-6, and the input terminals Ti2 to Ti7. As is clear from the above description, the entirety of the circuit which is the object of the test pattern generation includes cones equal to the number of its output terminals.
Although not shown in FIG. 12, in a scannable object circuit for test pattern generation, scannable flip-flops (abbreviated as FFs hereinafter) included in the circuit are handled as objects completely equivalent to the input or output terminals. In other words, those components to which logical values can be set or referred to from the outside of the circuit are handleable as being completely equivalent to the input or output terminals. Accordingly, if a scanning FF is arrived at when tracing a circuit in the direction from an output terminal toward the input terminal, the scanning FF can be regarded as equivalent to an input terminal as well as an output terminal, so that a new cone can be defined with the scanning FF as a starting point. Incidentally, in order to avoid complication, only circuits which do not include scanning FFs will be described in the following unless otherwise noted, but the discussion is applicable completely analogously to the circuits including scanning FFs that are equivalent to the input and output terminals.
FIG. 13 is a block diagram showing the important parts of the configuration of a test pattern generating system as a Related Art, which is not Prior Art. In the figure, a local CPU 1L corresponds to the CPU on the EWS 1-0 in FIG. 11, and a remote CPU 1R corresponds to a CPU mounted on either one of the EWSs 1-1 to 1xe2x80x94n in FIG. 11. A circuit information storage part 11 stores circuit information describing the kind of the input terminals, output terminal, and logic gates and the connection relationship among them. An external output terminal list preparing part 12 extracts all the output terminals from the circuit information stored in the circuit information storage part 11, and stores data of these output terminals in an external output terminal list storage part 13. In a circuit made scannable, the external output terminal list preparing part 12 extracts also the scanning FFs in addition to the output terminals. A subcircuit generating part 14 constructs subcircuits from the cones included in the entire circuit based on the storage contents of the circuit information storage part 11 and the storage contents of the external output terminal list storage part 13, and stores the result in a subcircuit storage part 15.
Moreover, a fault information storage part 16 stores all fault information to be detected for the entire circuit. A pattern ungenerated fault list control part 17 updates the storage contents of fault information for which test patterns are not yet generated so as for the contents to be held in a pattern ungenerated fault list storage part 18, based on the storage contents of the fault information storage part 16 and the storage contents of a pattern generated fault information storage part 27 (to be described later). When a test pattern generation of a subcircuit is requested to a certain remote CPU, a subcircuit fault list preparing part 19 prepares a list of faults included in the subcircuit based on the storage contents of the subcircuit storage part 15 related to the subcircuit and the storage contents of the pattern ungenerated fault list storage part 18, and stores the result in a subcircuit fault list storage part 20. A remote CPU assignment control part 24 manages the execution conditions of each remote CPU 1R, and selects an idle remote CPU 1R and requests that remote CPU 1R to generate a test pattern by handing over the circuit information and the fault list related to the generated subcircuit. In addition, the remote CPU assignment control part 24 communicates with various parts of the local CPU 1L via signal lines, not shown in the figure, and realizes such a processing as completion decision of the test pattern generation or the like.
In the meantime, in the remote CPU 1R, an automatic test pattern generating part 25 generates test patterns corresponding to respective fault information contained in the fault list based on the subcircuit information (the subcircuit storage part 15) and the fault list (the subcircuit fault list storage part 20) handed over from the local CPU 1L. As a result, the automatic test pattern generating part 25 stores the generated test patterns in a test pattern storage part 26, and stores pieces of fault information in the received fault list that are no longer required to be processed in the pattern generated fault information storage part 27 as pattern generated fault information. Here, the pattern generated fault information includes, besides pieces of fault information for which test patterns were actually generated, fault information for which the processing was dropped because of difficulty in generating test patterns, fault information which became clear that generation of test patterns is impossible in either one of the cones due to redundancy of the circuits, and the like. As to fault information for which test patterns were not generated under these circumstances, information indicating the reasons why test patterns were not generated are additionally stored in the pattern generated fault information storage part 27.
A pattern merge part 21 provided in the local CPU 1L combines test patterns generated in every remote CPU 1R and test patterns stored in a test pattern output part 28, and stores sequentially the generated test patterns in the test pattern output part 28. Besides, the pattern ungenerated fault list control part 17 outputs fault information for which test patterns were not generated to a pattern ungenerated fault list output part 29 at the point in time when the test pattern generation processing was conducted for all subcircuits contained in the entire circuit. In that case, the pattern ungenerated fault list control part 17 stores the reasons why test patterns were not generated in addition to a pattern ungenerated fault list. The reasons why test patterns were not generated includes such a situation that test pattern generation for unprocessed fault information is no longer needed because an expected fault detection rate has been attained, that the test pattern generation was given up because of an enormous amount of processing time required, that the test pattern generation was impossible because of the redundancy of the circuit, or the like.
In FIG. 14 which shows a more detailed constitution of the subcircuit generating part 14 shown in FIG. 13, constituent elements the same as those in FIG. 13 are given identical symbols. In the figure, a cone extracting part 31 randomly selects one output terminal which is not yet taken out of output terminals stored in the external output terminal list storage part 13, in order to add a cone to the subcircuits. The cone extracting part 31 finds a cone corresponding to the selected output terminal based on the storage contents of the circuit information storage part 11, and stores the circuit information on the cone to a cone storage part 32. In the meantime, the gate number and the circuit information of a subcircuit being on the process of generation are stored in the subcircuit storage part 15.
A subcircuit gate number counting part 33 adds the cone extracted on the cone storage part 32 to the subcircuits on the subcircuit storage part 15. In other words, the subcircuit gate number counting part 33 takes out the circuit information on the cone from the cone storage part 32 to calculate its gate number, and adds it to the gate number of the subcircuit on the subcircuit storage part 15 to updates the total gate number of the subcircuits being on the way to generation. In that case, the subcircuit gate number counting part 33 will not count the gate numbers of logic gates overlapping between cones into the total gate number of the subcircuit. Moreover, the subcircuit gate number counting part 33 adds the circuit information of the cone taken out to the circuit information of the subcircuits on the subcircuit storage part 15. Furthermore, the subcircuit gate number counting part 33 examines whether the total gate number of the updated subcircuits reached the prescribed value, and stops the cone selection operation by giving an indication to the cone extracting part 31 at the point in time when that condition is fulfilled. In this way, the subcircuit information to be given to the remote CPU 1R is generated on the subcircuit storage part 15. The subcircuit gate number counting part 33 initializes the total gate number of the subcircuit on the subcircuit storage part 15 to xe2x80x9c0xe2x80x9d, and initializes the circuit information to the empty state whenever generation of a subcircuit is started anew.
FIG. 15 is a flow chart showing the procedure of test pattern generation executed in the test pattern generating system having the above constitution. First, circuit information and fault information for an objective circuit of test pattern generation are stored in the circuit information storage part 11 and the fault information storage part 16, respectively (step S1). Next, when test pattern generation is indicated to the local CPU 1L, the external output terminal list preparing part 12 prepares an external output terminal list by extracting all output terminals from the circuit information. The subcircuit generating part 14 selects randomly one output terminal which has not yet been selected from among generated external output terminals, and find the cone corresponding to the output terminal (step S2). Then, the subcircuit generating part 14 adds the selected cone to the subcircuits to be generated (step S3), and calculates the gate number of the subcircuit to decide whether the total gate number of the subcircuits on its way to generation reached the prescribed value (step S4). If the total gate number of the subcircuits is not reaching the prescribed value (the decision result is xe2x80x9cNoxe2x80x9d), step S2 to step S4 are repeated until the prescribed value is reached (the decision result is xe2x80x9cYesxe2x80x9d). In this way, cones are randomly selected one by one and subcircuit generated by the subcircuit generating part 14 is added up sequentially to obtain subcircuits with sufficiently large size. When the cones to be taken out from the objective circuit for test pattern generation are exhausted, the subcircuit generating part 14 decides the subcircuits at that point in time to be the final subcircuits even if the total gate number of the subcircuit being on its way to generation is not reaching the prescribed value.
In the meantime, the pattern ungenerated fault list control part 17 prepares a pattern ungenerated fault list for the entire circuit based on the given fault information, and stores it in the pattern ungenerated fault list storage part 18. Then, whenever the subcircuit generating part 14 generates a subcircuit, the subcircuit fault list preparing part 19 prepares a list of pattern ungenerated faults contained in the generated subcircuit, while referring to the storage contents of the pattern ungenerated fault list storage part 18, and stores the result in the subcircuit fault list storage part 20 (step S5). Next, the remote CPU assignment control part 24 selects either one of the generated subcircuits, reads the circuit information and the fault list related to the subcircuit from the subcircuit storage part 15 and the subcircuit fault list storage part 20, respectively, and retrieves a remote CPU 1R in idle state to hand the subcircuit information and the fault list over to the remote CPU 1R (step S6). In the remote CPU 1R, the automatic test pattern generating part 25 generates a test pattern for the selected subcircuit (step S7) and stores the result in the test pattern storage part 26, and stores the list of test pattern generated fault information in the pattern generated fault information storage part 27.
When either one remote CPU 1R which has been in the process of test pattern generation completes the processing, the remote CPU sends back the generated test pattern and the pattern generated fault information to the local CPU (step S8). Then, in the local CPU 1L, the pattern ungenerated fault list control part 17 deletes the pattern generated fault information sent back from the pattern ungenerated fault list for the entire circuit which has been stored in the pattern ungenerated fault list storage part 18. At this time, the pattern ungenerated fault list control part 17 calculates the fault detection rate for the entire circuit based on the updated pattern ungenerated fault list. In addition, the pattern merging part 21 adds the test pattern sent back to the test patterns stored (in this case there is none since this is the first time) in the test pattern output part 28 (step S9).
Next, the remote CPU assignment control part 24 decides whether the fault detection rate calculated by the pattern ungenerated fault list control part 17 reached the predetermined target value (95%, for example), and inquires the subcircuit generating part 14 whether there are still remaining unprocessed cones in the objective circuit for test pattern generation. If there still remains some unprocessed cones and the fault detection rate is not reaching the target value (the decision result in step S10 being xe2x80x9cNoxe2x80x9d), the processes in step S2 to step S10 are repeated, and assigns a subcircuit to a remote CPU 1R in idle state. Thereafter, when the decision result of step S10 becomes xe2x80x9cYesxe2x80x9d by either the fault detection rate attained the target value or the unprocessed cones are exhausted, the remote CPU assignment control part 24 designates the pattern ungenerated fault list control part 17 to transfer the pattern ungenerated fault list stored in the pattern ungenerated fault list storage part 18 to a pattern ungenerated fault list output part 29. As a result, it becomes possible to take out the test patterns and the pattern ungenerated fault list (step S11).
As in the above, according to the related test pattern generating system to the present invention, in the process of generating a subcircuit by bundling a plurality of cones, no consideration whatsoever is given to the order of selecting these cones, and the cones are selected utterly randomly from among the cones existing in the objective circuit for test pattern generation. Because of this, the following drawbacks arise in the related test pattern generating system, which are causing waste of the processing time. Namely, when a subcircuit is formed by collecting the cones, depending upon the constitution of the objective circuit for test pattern generation, there arise overlapped portions in which input terminals or gates are shared and overlapped between the cones (or between the subcircuits including the cones) as shown by region A in FIG. 12. In such a case, when a test pattern is generated first for either one of the cone 6-1 and 6-2, the fault information in which a test pattern is generated in the first test pattern generation process is excluded from the pattern ungenerated fault list for the entire circuit, and is put outside the processing objects in the test pattern generation process thereafter. For example, if the cone 6-2 is processed first, and test patterns are generated for all faults within the region A, then in the later test pattern generation of the cone 6-1, test pattern generation will be performed with the fault list from which the fault information included in the region A is removed, as the object.
The relationship between the scale of the cone (assumed to be the gate number here) and the processing time required for test pattern generation for the cone is known to be not a simple proportionality but is, for example, exponential. Because of this, if attention is focused on the processing time required for test pattern generation for the region A in FIG. 12, the time required in test pattern generation for the cone 6-2 is longer than that for the cone 6-1 in spite of test pattern generations for the identical region. That is, for a region of overlap between the cones, the total processing time is smaller when test pattern generation is performed first for the cone with smaller number of gates than in the case of performing test pattern generation for the cone with larger number of gates.
When a subcircuit is constructed by selecting cones in random order as is done in the related method, in the region where cones overlap, there will frequently occur cases in which test pattern generation is processed first for the cone having a larger number of gates. In other words, wasteful processing time is consumed by performing test pattern generation without giving priority to the cone having smaller number of gates. Such a drawback is not limited to the mode in which test pattern generation is charged to a plurality of CPUs as shown in FIG. 11, but it can happen also in a mode, for example, where test pattern generation is performed successively using a single CPU.
In addition, in the distributed processing of test pattern generation using a plurality of CPUs as shown in FIG. 11, the following problem will arise due to the fact that the related test pattern generating system does not pay attention to the overlap of the cones. Assume a case as shown in FIG. 16 that, while a certain remote CPU is performing test pattern generation for a subcircuit 7, a remote CPU other than the original remote CPU goes to the idle state and a subcircuit is assigned to this idle remote CPU. Assume further that only either one of cones 6-3 and 6-4 is added to a subcircuit to be newly generated. In that case, selection of the cone 6-3 which has a smaller region of overlap with the subcircuit 7 results in a smaller number of test patterns generated by the overlapping between the subcircuits to be newly generated and the subcircuit 7. Since, however, the related method takes no consideration on the overlap between the cones or the subcircuits, there is a possibility that a subcircuit including the cone 6-4 is assigned first and processed. Because of this, surplus test patterns are generated which produces a problem similar to that pointed out in the above, reducing the effect of distributed processing.
Furthermore, in the related test pattern generating system, the following drawbacks are generated due to the distributed processing of test pattern generation. Consider, for example, the case in which two EWSs are generating test patterns in parallel for subcircuits including respectively the cones 6-1 and 6-2 shown in FIG. 12. In this case, since no consideration is given to the overlap between the cones in the related test pattern generating system, concerning the fault information included in the region A, test patterns are generated in duplicate by the two EWSs almost at the same time. However, for a certain fault, it suffices to generate a test pattern only for either one subcircuit, and frequent occurrence of multiple generation of test patterns reduces the effect of distributed processing using a plurality of EWSs. In other words, not only a memory capacity for storing the test patterns and the processing time for generating the test patterns are required correspondingly, but also a longer test time is required in testing the circuit using the generated test patterns.
It is an object of the invention to provide a novel method of generating test patterns for a logic circuit, a novel system performing the method, and a novel computer readable medium instructing the system to perform the method.
It is an-other object of the present invention to provide a method and a system for test pattern generation which can reduce the processing time required for test pattern generation by considering the order of processing the subcircuits when the test patterns are generated using the technique of circuit division.
It is further object of this invention to provide a method and a system for test pattern generation which can reduce the processing time for test pattern generation by considering the overlap between a subcircuit already processed and a cone to be added to a subcircuit currently under generation when the test patterns are generated by using the technique of distributed processing along with the technique of circuit division.
It is further object of this invention to provide a method and a system for test pattern generation which can further reduce the processing time by eliminating the overlapping between subcircuits to be processed distributedly when the test patterns are generated by using the technique of distributed processing along with the technique of circuit division.